

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item>{
	private Node<Item> firstNode;
	private Node<Item> lastNode;
	private int size=0;
	private static class Node<T>{
		T value;
		Node<T> nextNode;
		Node<T> previousNode;
		public Node(T value){
			this.value = value;
		}
	}

	public Deque(){

	}
	public void addFirst(Item item){
		checkNull(item);
		Node<Item> temp =  firstNode;
		firstNode = new Node<Item>(item);
		firstNode.nextNode = temp;		
		if(size == 0){
			lastNode = firstNode;
		}
		else{
			temp.previousNode = firstNode;
		}
		size++;
	}
	public void addLast(Item item){
		checkNull(item);
		Node<Item> temp =  lastNode;
		lastNode = new Node<Item>(item);
		lastNode.previousNode = temp;		
		if(size==0){
			firstNode = lastNode;
		}
		else{
			temp.nextNode = lastNode;
		}
		size++;
	}
	public Item removeFirst(){
		checkEmpty();
		Node<Item> temp = firstNode;
		firstNode = firstNode.nextNode;
		if(null!=firstNode){
			firstNode.previousNode = null;
		}
		else{
			lastNode = null;
		}
		size--;
		return temp.value;
	}
	public Item removeLast(){
		checkEmpty();
		Node<Item> temp = lastNode;
		lastNode = lastNode.previousNode;
		if(null!=lastNode){
			lastNode.nextNode = null;
		}
		else{
			firstNode = null;
		}
		size--;
		return temp.value;
	}
	private void checkEmpty(){
		if(isEmpty())
			throw new NoSuchElementException("Empty Deque");
	}
	private void checkNull(Item item){
		if(null==item){
			throw new NullPointerException("Can't add null");
		}
	}
	public boolean isEmpty(){
		return size == 0;
	}
	public int size(){
		return size;
	}
	public static void main(String[] args){
		Deque<String> deq = new Deque<String>();
		deq.addFirst("test");
		//deq.removeFirst();
		deq.addLast("test1");
		//deq.addFirst("test2");
		//deq.addFirst("test2");
		deq.removeLast();

		deq.addLast("test12");
		//deq.removeLast();
		deq.removeFirst();
		deq.addFirst("test13");

		deq.removeFirst();
		//deq.removeFirst();
		//deq.removeLast();
		System.out.println("Size="+deq.size);
		for(String str:deq){
			System.out.println(str);
		}

	}
	public Iterator<Item> iterator() {
		return new DequeIterator();
	}

	private class DequeIterator implements Iterator<Item>{
		private Node<Item> node;
		public DequeIterator() {
			this.node  = firstNode;
		}

		public boolean hasNext() {
			return node!=null;
		}

		public Item next() {
			if(!hasNext()){
				throw new NoSuchElementException("Empty!!");
			}
			Node<Item> returnNode = node;
			node = node.nextNode;
			return returnNode.value;
		}

		public void remove() {
			throw new UnsupportedOperationException("Not supported");

		}

	}
}